package 力扣._00周赛._145双周赛.问题3;

import java.util.HashSet;
import java.util.Set;

class Solution {
    // 判断素数
    boolean isPrime(int n) {
        if (n == 1)
            return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    // 回溯
    int min = Integer.MAX_VALUE;
    void backtrace(int[] n_nums, int[] m_nums, int now, Set<Integer> set) {
        if(now > min || isPrime(nums2num(n_nums)))
            return;
        // 判断是否相等
        if (n_nums[0] == m_nums[0] && n_nums[1] == m_nums[1] && n_nums[2] == m_nums[2]) {
            min = now;
            System.out.println(min);
            return;
        }

        // 在不同的位置上，选择某个数位+1，-1
        for (int i = 0; i < 3; i++) {
            if(n_nums[i] < 9 ){

                n_nums[i]++;
                if(!set.contains(nums2num(n_nums))){
                    set.add(nums2num(n_nums));
                    backtrace(n_nums, m_nums, now + nums2num(n_nums), set);
                }
                n_nums[i]--;
            }
        }
        for (int i = 0; i < 3; i++) {

            if(n_nums[i]>0 ){
                n_nums[i]--;
                if(!set.contains(nums2num(n_nums))){
                    set.add(nums2num(n_nums));
                backtrace(n_nums, m_nums, now + nums2num(n_nums), set);
                }
                n_nums[i]++;
            }

        }

    }

    // 数转数位数组
    int[] num2nums(int num) {
        int[] nums = new int[3];
        for (int i = 0; i < 3; i++) {
            nums[i] = num % 10;
            num /= 10;
        }
        return nums;
    }

    // 数位数组转数
    int nums2num(int[] nums) {
        int num = 0;
        for (int i = 2; i >= 0; i--) {
            num = num * 10 + nums[i];
        }
        return num;
    }

    public int minOperations(int n, int m) {
        // 数位长度最长为4，那还是回溯吧
        int[] n_nums = num2nums(n);
        int[] m_nums = num2nums(m);
        Set<Integer> set = new HashSet<>();
        backtrace(n_nums, m_nums, 0, set);
        if(min==Integer.MAX_VALUE)
            return -1;
        return min;



    }

    public static void main(String[] args) {
        System.out.println(new Solution().minOperations(10, 12));
    }
}